package leetcode.day_2021_03_8_2021_03_14;

/**
 * 45. 跳跃游戏 II
 * https://leetcode-cn.com/problems/jump-game-ii/
 * 输入: [2,3,1,1,4]
 * 输出: 2
 */
public class LeetCode0045 {

    // 此方法最后一个测试样例超时
    public static int jump(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = 0;
        for (int i=1; i<nums.length; i++) {
            dp[i] = min_steps(dp, nums, i);
        }
        return dp[nums.length-1];
    }

    public static int min_steps(int[] dp, int[] nums, int index) {
        int min = Integer.MAX_VALUE;
        for (int i=index-1; i>=0; i--) {
            if (index-i <= nums[i]) {
                min = Math.min(min, dp[i]+1);
            }
        }
        return min;
    }

    public static int jump2(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = 0;
        for (int i=1; i<nums.length; i++) {
            dp[i] = min_steps2(dp, nums, i);
        }
        return dp[nums.length-1];
    }

    /**
     * 从前往后找
     * @param dp
     * @param nums
     * @param index
     * @return
     */
    public static int min_steps2(int[] dp, int[] nums, int index) {
        int min = Integer.MAX_VALUE;
        for (int i=0; i<=index-1; i++) {
            if (index-i <= nums[i]) {
                min = Math.min(min, dp[i]+1);
            }
        }
        return min;
    }


    public static void main(String[] args) {
        System.out.println(jump2(new int[]{2,3,1,1,4,5}));
    }
}
